The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?



In [5]:

    
N = 1000000

def FastPrimeSieve(max): # From http://rebrained.com/?p=458
    possible_primes = list(range(3, max + 1, 2))
    curr_index = -1
    max_index = len(possible_primes)
    for latest_prime in possible_primes:
        curr_index +=1
        if not latest_prime: 
            continue
        for index_variable_not_named_j in range((curr_index+latest_prime),max_index, latest_prime): 
            possible_primes[index_variable_not_named_j]=0
    possible_primes.insert(0,2)
    return list(filter(None, possible_primes))

P = FastPrimeSieve(N)
n = len(P)
S = [0]*(n+1)
for i in range(n):
    S[i+1] = S[i] + P[i]
P = set(P)
first = 0
last = 1
max_run = 0
best_prime = 0

while last < n:
    diff = S[last] - S[first]
    run = last - first
    if run > max_run and diff < N and diff in P:
        max_run = run
        best_prime = diff
    if diff < N:
        last += 1
    else:
        first += 1
        last = first + max_run

print(best_prime)



In [ ]: